package 中等.搜索.广度优先搜索;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，
 * 我们可以获得一个新的字符串。
 * 返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/letter-case-permutation/
 */
public class 字母大小写全排列_784 {

    public static void main(String[] args) {

        System.out.println(letterCasePermutation("a1b2"));

    }

    /**
     * 广度优先搜索
     *
     * @param s
     * @return
     */
    public static List<String> letterCasePermutation(String s) {
        List<String> list = new ArrayList<>();

        char[] chars = s.toCharArray();
        Deque<String> queue = new ArrayDeque<>();
        queue.addLast(String.valueOf(chars[0]));
        if (Character.isLetter(chars[0]) ||
                Character.isUpperCase(chars[0])) {
            queue.addLast(String.valueOf(chars[0] ^= 32));
        }

        for (int i = 1; i < chars.length; i++) {
            int size = queue.size();
            while (size-- > 0) {
                String preStr = queue.pollFirst();

                StringBuilder pre1 = new StringBuilder();
                pre1.append(preStr);
                StringBuilder pre2 = new StringBuilder();
                pre2.append(preStr);

                queue.addLast(pre1.append(chars[i]).toString());
                if (Character.isLetter(chars[i]) ||
                        Character.isUpperCase(chars[i])) {
                    queue.addLast(pre2.append(chars[i] ^= 32).toString());
                }
            }
        }

        while (!queue.isEmpty()) {
            list.add(queue.pollFirst());
        }
        return list;
    }

}
